class QuadTree {
  constructor(lvl, pBounds, ctx) {
    this.level = lvl;
    this.bounds = { ...pBounds };
    this.ctx = ctx;
    this.objects = [];
    this.nodes = [];
  }
  ctx = null;
  MAX_OBJECT = 3;
  MAX_LEVEL = 5;

  level;
  objects;
  nodes;

  bounds = {
    x: 0,
    y: 0,
    width: 0,
    height: 0,
  };

  clear() {
    this.objects = [];
    for (let i = 0; i < this.nodes.length; i++) {
      this.nodes[i].clear();
    }
    this.nodes = [];
  }

  split() {
    this.nodes = new Array(4);

    let subWidth = this.bounds.width / 2;
    let subHeight = this.bounds.height / 2;

    this.nodes[0] = new QuadTree(
      this.level + 1,
      {
        x: this.bounds.x + subWidth,
        y: this.bounds.y,
        width: subWidth,
        height: subHeight,
      },
      this.ctx
    );
    this.nodes[1] = new QuadTree(
      this.level + 1,
      {
        x: this.bounds.x,
        y: this.bounds.y,
        width: subWidth,
        height: subHeight,
      },
      this.ctx
    );
    this.nodes[2] = new QuadTree(
      this.level + 1,
      {
        x: this.bounds.x,
        y: this.bounds.y + subHeight,
        width: subWidth,
        height: subHeight,
      },
      this.ctx
    );
    this.nodes[3] = new QuadTree(
      this.level + 1,
      {
        x: this.bounds.x + subWidth,
        y: this.bounds.y + subHeight,
        width: subWidth,
        height: subHeight,
      },
      this.ctx
    );
    this.drawLine(
      { x: this.bounds.x + subWidth, y: this.bounds.y },
      { x: this.bounds.x + subWidth, y: this.bounds.y + this.bounds.height }
    );
    this.drawLine(
      { x: this.bounds.x, y: this.bounds.y + subHeight },
      { x: this.bounds.x + this.bounds.width, y: this.bounds.y + subHeight }
    );
  }

  getIndex(pBounds) {
    let index = -1;
    let verticalMidpoint = this.bounds.x + this.bounds.width / 2;
    let horizontialMidpoint = this.bounds.y + this.bounds.height / 2;
    let topQuadrant =
      pBounds.y > this.bounds.y &&
      pBounds.height + pBounds.y < horizontialMidpoint;
    let bottomQuadrant = pBounds.y > horizontialMidpoint;
    if (topQuadrant) {
      if (
        pBounds.x > this.bounds.x &&
        pBounds.width + pBounds.x < verticalMidpoint
      ) {
        index = 1;
      } else if (pBounds.x > verticalMidpoint) {
        index = 0;
      }
    } else if (bottomQuadrant) {
      if (
        pBounds.x > this.bounds.x &&
        pBounds.width + pBounds.x < verticalMidpoint
      ) {
        index = 2;
      } else if (pBounds.x > verticalMidpoint) {
        index = 3;
      }
    }
    //debugger
    return index;
  }

  insert(pBounds) {
    if(this.nodes.length != 0){
      let index = this.getIndex(pBounds);
      if(index != -1){
        this.nodes[index].insert(pBounds);
        return;
      }
    }
   
    this.objects.push({ ...pBounds });

    if (this.nodes.length === 0 && this.objects.length > this.MAX_OBJECT && this.level < this.MAX_LEVEL) {
      //分割当前区域
      this.split();

      let tempobjects = [];
      for (let i = 0; i < this.objects.length; i++) {
        let idx = this.getIndex(this.objects[i]);
        if (idx != -1) {
          this.nodes[idx].insert(this.objects[i]);
        } else if (idx === -1) {
          tempobjects.push({ ...this.objects[i] });
        }
      }
      this.objects = [...tempobjects];
    }
  }

  queryQuadTree(resultList, pBounds) {
    let index = this.getIndex(pBounds);
    if (index != -1 && this.nodes.length != 0) {
      this.nodes[index].queryQuadTree(resultList, pBounds);
    }
    //console.log("lvl:" + this.level + "\n" + "物体数:" + this.objects.length);

    resultList = [...resultList, ...this.objects];
    return resultList;
  }

  drawLine(startPos, endPos) {
    ctx.fillStyle = "#12d269";
    ctx.beginPath();
    ctx.moveTo(startPos.x, startPos.y);
    ctx.lineTo(endPos.x, endPos.y);
    ctx.stroke();
  }
}
